//二叉搜索树   就是如果该节点存在左子树，则左子树小于该节点   如果该节点存在右子树，则左子树大于根节点
public class HashBuck {
    static  class Node{
        public  int key;
        public  int val;
        public  Node next;
        public Node(int key,int val){
            this.key=key;
            this.val=val;
        }
    }
    public  Node[]arrY;
    public  int usedSize;
    public  HashBuck(){
        arrY=new Node[10];
    }
    public  void put(int key,int val){
        int index=key%arrY.length;
        Node cur=arrY[index];
        while (cur!=null){
            if(cur.key==key){
                cur.val=val;
                return;
            }
            cur=cur.next;
        }
        Node node=new Node(key,val);
        node.next=arrY[index];
        arrY[index]=node;
        usedSize++;
        if(loadFactor()>=0.75){
            resize();
        }
    }
    private  void resize(){
        Node[]tmpArr=new Node[arrY.length*2];
        for (int i = 0; i < arrY.length; i++) {
            Node cur=arrY[i];
            while (cur!=null){
                Node curNext=cur.next;
                int newIndex=cur.key%tmpArr.length;
                cur.next=tmpArr[newIndex];
                tmpArr[newIndex]=cur;
                cur=curNext;
            }
        }
        arrY=tmpArr;
    }
    private  double loadFactor(){
        return  usedSize*1.0/arrY.length;
    }
    public int get (int key){
        int index=key%arrY.length;
        Node cur=arrY[index];
        while (cur!=null){
            if(cur.key==key){
                return cur.val;
            }
            cur=cur.next;
        }
        return -1;
    }
}
